Purpose shapFlex logo

The purpose of shapFlex, short for Shapley flexibility, is to compute stochastic feature-level Shapley values for ensemble models using potentially different, high-dimensional input datasets. The main function in this package is shapFlex::shapFlex().

Benefits

  • Flexibility:
    • Shapley values can be estimated for ensembles of many machine learning models using a simple user-defined predict() wrapper function.
    • Shapley values can be estimated for a given feature if it appears in multiple datasets in a more elaborate ensemble model.
  • Speed:
    • The code itself hasn’t been optimized for speed. The speed advantage of shapFlex comes in the form of giving the user the ability to select 1 or more target features of interest and avoid having to compute Shapley values for all model features. This is especially useful in high-dimensional models as the computation of a Shapley value is exponential in the number of features.


Package Features

  1. Compute ensemble Shapley values for select features with shapFlex::shapFlex().

Background

As algorithmic decision-making continues its headlong rush into our everyday lives, interpretable machine learning has become increasingly relevant for society, machine/deep learning researchers, and data science practicioners alike (1). And while numerous statistical techniques and methodologies have been dedicated to making black-box models and the decisions that they produce more human-friendly, one method in particular, the Shapley value, has a number of desirable properties including its ability to unify several seemingly different methodologies (2).

Briefly, in the context of machine learning, a Shapley value represents the marginal or unique contribution of each model feature toward each prediction. It’s a hyper-local measure of feature importance for each individual or instance which gives a clear profile of how a prediction model is uniquely making predictions for a given instance. Shapley values are measured in the same units in which your model is making predictions: dollars, number of cats, risk, probability etc. The Shapley method of feature influence has a number of practical applications which include (a) detecting bias in machine learning models, (b) training and tuning models by assessing the Shapley values of influential observations, and (c) using the resulting ‘instance * feature’ matrix as an input for a variety of additional machine learning tasks such as clustering.

Below are several good resources to learn more about the features, benefits, and uses of Shapley values for interpreting black-box machine learning models:


Example

  • We’ll demonstrate how to use the shapFlex package with a worked example using the imports85 dataset from the randomForest package.

  • Our goal is to see how each of ~20 factors in a simple machine learning ensemble model uniquely influence the price of a car using approximate Shapley values.

  • The Shapley values will be plotted (a) across all investigated samples/cars to get a measure of global feature importance and (b) for select cars to get a measure of local feature importance.

Install shapFlex

devtools::install_github("nredell/shapFlex")
library(shapFlex)


Load packages and data

library(glmnet)
library(randomForest)
library(ggplot2)
library(plotly)
library(DT)

data("imports85", package = "randomForest")
data <- imports85

data <- data[, -2]  # this column has excessive missing data.
data <- data[complete.cases(data), ]
row.names(data) <- 1:nrow(data)  # re-index for simplicity.

DT::datatable(head(data, 5), options = list(scrollX = TRUE))


Train models

  • Outcome: price

  • Features: ~20

  • Sample size: ~200

  • Models: A LASSO from glmnet and a Random Forest from randomForest.
outcome_col <- which(names(data) == "price")
outcome_name <- names(data)[outcome_col]

model_formula <- formula(paste0(outcome_name,  "~ ."))

set.seed(224)
model_lasso <- glmnet::cv.glmnet(x = model.matrix(model_formula, data), 
                                 y = as.matrix(data[, outcome_col, drop = FALSE], ncol = 1))

set.seed(224)
model_rf <- randomForest::randomForest(formula = model_formula, data = data, ntree = 200)


Prepare shapFlex::shapFlex() Input

User-defined prediction function

  • Required: A user-defined wrapper function that takes the following positional arguments:
    • Position 1: A list of model objects for predicting on the input dataset.
    • Position 2: A data.frame of model features (the outcome column won’t be passed in shapFlex()).

      and returns:

    • A 1-column data.frame with a number of rows equal to the input data.

  • This function can be simple–like below–or contain meta-models for combining ensemble predictions, feature transformations, or model stacking etc.
# models[1] and models[2] could be hardcoded model_lasso and model_rf.
# In the next code block, see the `model_list` object for an example of the format of the 'models' argument.
predict_ensemble <- function(models, data, ...) {
  
  y_pred_lasso <- data.frame(predict(models[[1]], model.matrix(~ ., data)))  # LASSO
  y_pred_rf <- data.frame(predict(models[[2]], data))  # Random Forest
  
  data_pred <- dplyr::bind_cols(y_pred_lasso, y_pred_rf)
  
  data_pred <- data.frame("y_pred" = rowMeans(data_pred, na.rm = TRUE))
  
  return(data_pred)
}

Shapley sampling parameters

  • Below are some of the main arguments to shapFlex::shapFlex() with some context.

  • We’re going to explain all instances in our dataset using all features which is the default setting.

  • Refer to the–forthcoming–vignette to see how shapFlex::shapFlex() runtime and accuracy are affected by the number of model features and monte carlo sample size.

# A list of data.frame(s) of model features suitable for the user-defined predict function(s).
data_list <- list(data[, -(outcome_col), drop = FALSE])
# Dataset row numbers or indicies.
explain_instances <- 1:nrow(data)
# Are the instances to explain row numbers/indices or row names ('row_name') in the input data?
explain_instance_id <- "row_index"
# A list of of model objects. Nested lists of length(data_list) are needed if length(data_list) > 1.
model_list <- list(model_lasso, model_rf)
# A list of length 1 vectors with length(prediction_functions) == length(data_list).
predict_functions <- list("predict_ensemble")
# The number of randomly selected dataset rows used to calculate the feature-level Shapley values.
sample_size <- 100
# Number of cores to use in parallel::mclapply(); limited to 1 on Windows OS.
n_cores <- if (Sys.info()["sysname"] == "Windows") {1} else {parallel::detectCores() - 1}


shapFlex::shapFlex()

Explain with all model features

  • Because shapFlex::shapFlex() explains 1 dataset row/instance at a time, we’ll loop through our dataset and store the results in a list.

  • Let’s also record the runtime and compare it to the time it takes to explain with 1 feature.

explained_instances <- vector("list", length(explain_instances))

start <- Sys.time()
set.seed(224)
for (i in seq_along(explain_instances)) {
  
  explained_instances[[i]] <- shapFlex::shapFlex(data = data_list, 
                                                 explain_instance = explain_instances[i],  # loop
                                                 explain_instance_id = explain_instance_id,
                                                 models = model_list, 
                                                 predict_functions = predict_functions, 
                                                 sample_size = sample_size, 
                                                 n_cores = n_cores)
}
stop <- Sys.time()
list(stop - start, paste0("Cores = ", n_cores))
[[1]]
Time difference of 9.153347 mins

[[2]]
[1] "Cores = 1"


  • The output of shapFlex::shapFlex() is a data.frame with the following columns:
    • explained_instance: The row name or row number of the target instance (number/name depends on the ’explain_instance_id` argument).
    • feature_name: The feature name from names(data) or a subset of all features if using the ‘target_features’ argument. The intercept represents the average prediction in the input dataset–regardless of whether or not any models explicitly use intercepts.
    • feature_value: Taken from the input data. The intercept has an NA feature value. At present, only appears with 1 input dataset.
    • shap_effect: The average Shapley value across samples in ‘sample_size’.
    • shap_effect_sd: The standard deviation in Shapley values across samples in ‘sample_size’. At present, only appears with 1 input dataset.
data_shap <- dplyr::bind_rows(explained_instances)

DT::datatable(data_shap)

Global feature effects

  • Below are plots similar to partial dependence plots for categorical followed by numeric model features.
data_plot <- data_shap

factor_features <- names(data)[which(unlist(lapply(data, function(x) {methods::is(x, "factor")})))]

data_plot <- dplyr::filter(data_plot, feature_name %in% factor_features)

p <- ggplot(data_plot, aes(feature_value, shap_effect))
p <- p + geom_boxplot()
p <- p + scale_y_continuous(label = scales::dollar)
p <- p + facet_wrap(~ feature_name, scales = "free")
p <- p + theme_bw() + xlab(NULL) + ylab("Shapley value (0 is the average prediction)")
p

data_plot <- data_shap

numeric_features <- names(data)[which(unlist(lapply(data, function(x) {!methods::is(x, "factor")})))]

data_plot <- dplyr::filter(data_plot, feature_name %in% numeric_features)

data_plot$feature_value <- as.numeric(data_plot$feature_value)

p <- ggplot(data_plot, aes(feature_value, shap_effect))
p <- p + geom_point(alpha = .25)
p <- p + geom_smooth()
p <- p + scale_y_continuous(label = scales::dollar)
p <- p + facet_wrap(~ feature_name, scales = "free")
p <- p + theme_bw() + xlab(NULL) + ylab("Shapley value (0 is the average prediction)")
suppressWarnings(suppressMessages(print(p)))

Explain with 1 model feature

  • Now, let’s say we’re really interested in the marginal effect of horsepower on car prices but don’t have the time to compute Shapley values for all features.

  • In this case, we’ll set the ‘target_features’ argument and examine its effect.

  • The Shapley values are still calculated in the usual way, and the results are identical if a seed is set, but we get results 14 times faster.

explained_instances <- vector("list", length(explain_instances))

target_features <- list("horsepower")

start <- Sys.time()
set.seed(224)
for (i in seq_along(explain_instances)) {

  explained_instances[[i]] <- shapFlex::shapFlex(data = data_list, 
                                                 explain_instance = explain_instances[i],  # loop
                                                 explain_instance_id = explain_instance_id,
                                                 models = model_list, 
                                                 predict_functions = predict_functions, 
                                                 target_features = target_features, 
                                                 sample_size = sample_size, 
                                                 n_cores = n_cores)
}
stop <- Sys.time()
list(stop - start, paste0("Cores = ", n_cores))
[[1]]
Time difference of 40.19398 secs

[[2]]
[1] "Cores = 1"

Global feature effects

data_shap_var <- dplyr::bind_rows(explained_instances)

data_plot <- data_shap_var

numeric_features <- "horsepower"

data_plot <- dplyr::filter(data_plot, feature_name %in% numeric_features)

data_plot$feature_value <- as.numeric(data_plot$feature_value)

p <- ggplot(data_plot, aes(feature_value, shap_effect))
p <- p + geom_point(alpha = .25)
p <- p + geom_smooth()
p <- p + scale_y_continuous(label = scales::dollar)
p <- p + facet_wrap(~ feature_name, scales = "free")
p <- p + theme_bw() + xlab(NULL) + ylab("Shapley value (0 is the average prediction)")
suppressWarnings(suppressMessages(print(p)))

Feature subset consistency

  • Finally, we’ll check to see that the horsepower Shapley value estimates across our samples are identical when Shapley values are (a) computed for all features and (b) computed soley for horsepower.

  • As expected, the estimates are identical. If we are interested in focusing on horsepower and learning more about how the relationship between horsepower and a car’s price changes as (a) new models are added to the ensemble or (b) the model incorporates new features, we can do so without the overhead of computing Shapley values for all features.

horsepower_shap_all_features <- dplyr::filter(data_shap, feature_name == "horsepower") %>% 
  dplyr::select(shap_effect)
horsepower_shap_1_feature <- dplyr::filter(data_shap_var, feature_name == "horsepower") %>% 
  dplyr::select(shap_effect)

identical(horsepower_shap_all_features, horsepower_shap_1_feature)
[1] TRUE

Local feature importance

  • Because Shapley values give us insight into how each feature uniquely affects each instance’s prediction, we’ll produce a plot of the feature effects profile for a handful of instances.

  • Below is a plot of how each of the modeled features from our ensemble model is impacting predicted prices for the 6 Audis in the dataset (rows 4 through 9 in our filtered dataset).

  • Hover over the bars to see the feature values.

data_plot <- data_shap

audis <- which(data$make == "audi")

data_plot <- dplyr::filter(data_plot, explained_instance %in% audis)

data_plot$bar_color <- ifelse(data_plot$shap_effect >= 0, "increase", "decrease")

p <- ggplot(data_plot, aes(x = feature_name, y = shap_effect, fill = bar_color, 
                           group = explained_instance, text = paste0(feature_name, ": ", feature_value)))
p <- p + geom_bar(stat = "identity", show.legend = FALSE)
p <- p + scale_y_continuous(label = scales::dollar)
p <- p + facet_wrap(~ explained_instance)
p <- p + theme_bw() + theme(legend.position = "none") + coord_flip() + xlab(NULL) + ylab("Shapley value")
plotly::ggplotly(p, tooltip = "text")
LS0tDQp0aXRsZTogInBhY2thZ2U6OnNoYXBGbGV4IE92ZXJ2aWV3Ig0KZGF0ZTogImByIGx1YnJpZGF0ZTo6dG9kYXkoKWAiDQphdXRob3I6ICJOaWNrIFJlZGVsbCwgbmlja3JlZGVsbEBob3RtYWlsLmNvbSINCm91dHB1dDoNCiAgaHRtbF9ub3RlYm9vazoNCiAgICBjb2RlX2ZvbGRpbmc6IHNob3cNCiAgICB0b2M6IHllcw0KICAgIHRvY19mbG9hdDogeWVzDQotLS0NCg0KKioqDQoNCiMgUHVycG9zZSA8aW1nIHNyYz0ic2hhcEZsZXhfbG9nby5wbmciIGFsdD0ic2hhcEZsZXggbG9nbyIgYWxpZ249InJpZ2h0IiB3aWR0aD0iMTUwIiBoZWlnaHQ9IjE1MCIgc3R5bGU9ImRpc3BsYXk6IGlubGluZS1ibG9jazsgcGFkZGluZzogNXB4OyI+DQoNClRoZSBwdXJwb3NlIG9mIGBzaGFwRmxleGAsIHNob3J0IGZvciBTaGFwbGV5IGZsZXhpYmlsaXR5LCBpcyB0byBjb21wdXRlIHN0b2NoYXN0aWMgZmVhdHVyZS1sZXZlbCBTaGFwbGV5IHZhbHVlcyANCmZvciBlbnNlbWJsZSBtb2RlbHMgdXNpbmcgcG90ZW50aWFsbHkgZGlmZmVyZW50LCBoaWdoLWRpbWVuc2lvbmFsIGlucHV0IGRhdGFzZXRzLiBUaGUgbWFpbiBmdW5jdGlvbiBpbiB0aGlzIHBhY2thZ2UgaXMgYHNoYXBGbGV4OjpzaGFwRmxleCgpYC4NCg0KKioqDQoNCiMgQmVuZWZpdHMNCg0KKiAqKkZsZXhpYmlsaXR5Kio6IA0KICAgICsgU2hhcGxleSB2YWx1ZXMgY2FuIGJlIGVzdGltYXRlZCBmb3IgZW5zZW1ibGVzIG9mIDx1Pm1hbnkgbWFjaGluZSBsZWFybmluZyBtb2RlbHM8L3U+IHVzaW5nIGEgc2ltcGxlIHVzZXItZGVmaW5lZCBwcmVkaWN0KCkgd3JhcHBlciBmdW5jdGlvbi4NCiAgICArIFNoYXBsZXkgdmFsdWVzIGNhbiBiZSBlc3RpbWF0ZWQgZm9yIGEgZ2l2ZW4gZmVhdHVyZSBpZiBpdCBhcHBlYXJzIGluIDx1Pm11bHRpcGxlIGRhdGFzZXRzPC91PiBpbiBhIG1vcmUgZWxhYm9yYXRlIGVuc2VtYmxlIG1vZGVsLg0KPGJyPg0KKiAqKlNwZWVkKio6DQogICAgKyBUaGUgY29kZSBpdHNlbGYgaGFzbid0IGJlZW4gb3B0aW1pemVkIGZvciBzcGVlZC4gVGhlIHNwZWVkIGFkdmFudGFnZSBvZiBgc2hhcEZsZXhgIGNvbWVzIGluIHRoZSBmb3JtIG9mIGdpdmluZyB0aGUgdXNlciB0aGUgYWJpbGl0eSANCiAgICB0byA8dT5zZWxlY3QgMSBvciBtb3JlIHRhcmdldCBmZWF0dXJlcyBvZiBpbnRlcmVzdDwvdT4gYW5kIGF2b2lkIGhhdmluZyB0byBjb21wdXRlIFNoYXBsZXkgdmFsdWVzIGZvciBhbGwgbW9kZWwgZmVhdHVyZXMuIFRoaXMgaXMgZXNwZWNpYWxseSANCiAgICB1c2VmdWwgaW4gaGlnaC1kaW1lbnNpb25hbCBtb2RlbHMgYXMgdGhlIGNvbXB1dGF0aW9uIG9mIGEgU2hhcGxleSB2YWx1ZSBpcyBleHBvbmVudGlhbCBpbiB0aGUgbnVtYmVyIG9mIGZlYXR1cmVzLg0KDQoqKioNCg0KPGJyPg0KDQojIFBhY2thZ2UgRmVhdHVyZXMNCg0KMS4gQ29tcHV0ZSAqKmVuc2VtYmxlIFNoYXBsZXkgdmFsdWVzIGZvciBzZWxlY3QgZmVhdHVyZXMqKiB3aXRoIGBzaGFwRmxleDo6c2hhcEZsZXgoKWAuDQoNCioqKg0KDQojIEJhY2tncm91bmQNCg0KQXMgYWxnb3JpdGhtaWMgZGVjaXNpb24tbWFraW5nIGNvbnRpbnVlcyBpdHMgaGVhZGxvbmcgcnVzaCBpbnRvIG91ciBldmVyeWRheSBsaXZlcywgaW50ZXJwcmV0YWJsZSANCm1hY2hpbmUgbGVhcm5pbmcgaGFzIGJlY29tZSBpbmNyZWFzaW5nbHkgcmVsZXZhbnQgZm9yIHNvY2lldHksIG1hY2hpbmUvZGVlcCBsZWFybmluZyByZXNlYXJjaGVycywgDQphbmQgZGF0YSBzY2llbmNlIHByYWN0aWNpb25lcnMgYWxpa2UgKFsxXShodHRwczovL2FyeGl2Lm9yZy9hYnMvMTcwMi4wODYwOCkpLiBBbmQgd2hpbGUgbnVtZXJvdXMgc3RhdGlzdGljYWwgdGVjaG5pcXVlcyBhbmQgDQptZXRob2RvbG9naWVzIGhhdmUgYmVlbiBkZWRpY2F0ZWQgdG8gbWFraW5nIGJsYWNrLWJveCBtb2RlbHMgYW5kIHRoZSBkZWNpc2lvbnMgdGhhdCB0aGV5IA0KcHJvZHVjZSBtb3JlIGh1bWFuLWZyaWVuZGx5LCBvbmUgbWV0aG9kIGluIHBhcnRpY3VsYXIsIHRoZSBTaGFwbGV5IHZhbHVlLCBoYXMgYSBudW1iZXIgb2YgZGVzaXJhYmxlIA0KcHJvcGVydGllcyBpbmNsdWRpbmcgaXRzIGFiaWxpdHkgdG8gdW5pZnkgc2V2ZXJhbCBzZWVtaW5nbHkgZGlmZmVyZW50IG1ldGhvZG9sb2dpZXMgDQooWzJdKGh0dHA6Ly9wYXBlcnMubmlwcy5jYy9wYXBlci83MDYyLWEtdW5pZmllZC1hcHByb2FjaC10by1pbnRlcnByZXRpbmctbW9kZWwtcHJlZGljdGlvbnMucGRmKSkuIA0KDQpCcmllZmx5LCBpbiB0aGUgY29udGV4dCBvZiBtYWNoaW5lIGxlYXJuaW5nLCBhIFNoYXBsZXkgdmFsdWUgcmVwcmVzZW50cyB0aGUgbWFyZ2luYWwgb3IgdW5pcXVlIGNvbnRyaWJ1dGlvbiANCm9mIGVhY2ggbW9kZWwgZmVhdHVyZSB0b3dhcmQgZWFjaCBwcmVkaWN0aW9uLiBJdCdzIGEgPGI+aHlwZXItbG9jYWwgbWVhc3VyZSBvZiBmZWF0dXJlIGltcG9ydGFuY2U8L2I+IGZvciBlYWNoIA0KaW5kaXZpZHVhbCBvciBpbnN0YW5jZSB3aGljaCBnaXZlcyBhIGNsZWFyIHByb2ZpbGUgb2YgaG93IGEgcHJlZGljdGlvbiBtb2RlbCBpcyB1bmlxdWVseSBtYWtpbmcgDQpwcmVkaWN0aW9ucyBmb3IgYSBnaXZlbiBpbnN0YW5jZS4gU2hhcGxleSB2YWx1ZXMgYXJlIG1lYXN1cmVkIGluIHRoZSBzYW1lIHVuaXRzIGluIHdoaWNoIHlvdXIgbW9kZWwgaXMgDQptYWtpbmcgcHJlZGljdGlvbnM6IGRvbGxhcnMsIG51bWJlciBvZiBjYXRzLCByaXNrLCBwcm9iYWJpbGl0eSBldGMuIFRoZSBTaGFwbGV5IG1ldGhvZCBvZiBmZWF0dXJlIGluZmx1ZW5jZSANCmhhcyBhIG51bWJlciBvZiBwcmFjdGljYWwgYXBwbGljYXRpb25zIHdoaWNoIGluY2x1ZGUgKGEpIGRldGVjdGluZyBiaWFzIGluIG1hY2hpbmUgbGVhcm5pbmcgbW9kZWxzLCAoYikgdHJhaW5pbmcgYW5kDQp0dW5pbmcgbW9kZWxzIGJ5IGFzc2Vzc2luZyB0aGUgU2hhcGxleSB2YWx1ZXMgb2YgaW5mbHVlbnRpYWwgb2JzZXJ2YXRpb25zLCBhbmQgKGMpIHVzaW5nIHRoZSANCnJlc3VsdGluZyAnaW5zdGFuY2UgKiBmZWF0dXJlJyBtYXRyaXggYXMgYW4gaW5wdXQgZm9yIGEgdmFyaWV0eSBvZiBhZGRpdGlvbmFsIG1hY2hpbmUgbGVhcm5pbmcgdGFza3Mgc3VjaCBhcyBjbHVzdGVyaW5nLg0KDQpCZWxvdyBhcmUgc2V2ZXJhbCBnb29kIHJlc291cmNlcyB0byBsZWFybiBtb3JlIGFib3V0IHRoZSBmZWF0dXJlcywgYmVuZWZpdHMsIGFuZCB1c2VzIG9mIFNoYXBsZXkgdmFsdWVzIGZvciANCmludGVycHJldGluZyBibGFjay1ib3ggbWFjaGluZSBsZWFybmluZyBtb2RlbHM6DQoNCiogW0ludGVycHJldGFibGUgTWFjaGluZSBMZWFybmluZyBieSBDaHJpc3RvcGggTW9sbmFyXShodHRwczovL2NocmlzdG9waG0uZ2l0aHViLmlvL2ludGVycHJldGFibGUtbWwtYm9vay9zaGFwbGV5Lmh0bWwpDQoqIFtQeXRob24gc2hhcCBwYWNrYWdlIGJ5IFNjb3R0IEx1bmRiZXJnXShodHRwczovL2dpdGh1Yi5jb20vc2x1bmRiZXJnL3NoYXApDQoqIFtCbG9nIHBvc3QgZnJvbSB0aGUgYXV0aG9yIG9mIHNoYXBdKGh0dHBzOi8vdG93YXJkc2RhdGFzY2llbmNlLmNvbS9pbnRlcnByZXRhYmxlLW1hY2hpbmUtbGVhcm5pbmctd2l0aC14Z2Jvb3N0LTllYzgwZDE0OGQyNykNCg0KKioqDQoNCmBgYHtyLCBpbmNsdWRlID0gRkFMU0V9DQprbml0cjo6b3B0c19jaHVuayRzZXQoZmlnLndpZHRoID0gOSwgZmlnLmhlaWdodCA9IDYpDQpgYGANCg0KYGBge3IsIGluY2x1ZGUgPSBGQUxTRX0NCmRldnRvb2xzOjpsb2FkX2FsbChleHBvcnRfYWxsID0gRkFMU0UpDQpgYGANCg0KPGJyPg0KDQojIEV4YW1wbGUNCg0KKiBXZSdsbCBkZW1vbnN0cmF0ZSBob3cgdG8gdXNlIHRoZSBgc2hhcEZsZXhgIHBhY2thZ2Ugd2l0aCBhIHdvcmtlZCBleGFtcGxlIHVzaW5nIHRoZSBgaW1wb3J0czg1YCBkYXRhc2V0IGZyb20gdGhlIGByYW5kb21Gb3Jlc3RgIHBhY2thZ2UuDQo8cD4NCiogT3VyIGdvYWwgaXMgdG8gc2VlIGhvdyBlYWNoIG9mIH4yMCBmYWN0b3JzIGluIGEgc2ltcGxlIG1hY2hpbmUgbGVhcm5pbmcgZW5zZW1ibGUgbW9kZWwgdW5pcXVlbHkgDQppbmZsdWVuY2UgdGhlIHByaWNlIG9mIGEgY2FyIHVzaW5nIGFwcHJveGltYXRlIFNoYXBsZXkgdmFsdWVzLiANCjxwPg0KKiBUaGUgU2hhcGxleSB2YWx1ZXMgd2lsbCBiZSBwbG90dGVkIChhKSBhY3Jvc3MgYWxsIGludmVzdGlnYXRlZCBzYW1wbGVzL2NhcnMgdG8gZ2V0IGEgbWVhc3VyZSBvZiANCioqZ2xvYmFsIGZlYXR1cmUgaW1wb3J0YW5jZSoqIGFuZCAoYikgZm9yIHNlbGVjdCBjYXJzIHRvIGdldCBhIG1lYXN1cmUgb2YgKipsb2NhbCBmZWF0dXJlIGltcG9ydGFuY2UqKi4NCg0KDQojIyBJbnN0YWxsIHNoYXBGbGV4DQoNCmBgYHtyLCBldmFsID0gRkFMU0V9DQpkZXZ0b29sczo6aW5zdGFsbF9naXRodWIoIm5yZWRlbGwvc2hhcEZsZXgiKQ0KbGlicmFyeShzaGFwRmxleCkNCmBgYA0KDQo8YnI+DQoNCiMjIExvYWQgcGFja2FnZXMgYW5kIGRhdGENCg0KYGBge3IsIHdhcm5pbmcgPSBGQUxTRSwgbWVzc2FnZSA9IEZBTFNFfQ0KbGlicmFyeShnbG1uZXQpDQpsaWJyYXJ5KHJhbmRvbUZvcmVzdCkNCmxpYnJhcnkoZ2dwbG90MikNCmxpYnJhcnkocGxvdGx5KQ0KbGlicmFyeShEVCkNCg0KZGF0YSgiaW1wb3J0czg1IiwgcGFja2FnZSA9ICJyYW5kb21Gb3Jlc3QiKQ0KZGF0YSA8LSBpbXBvcnRzODUNCg0KZGF0YSA8LSBkYXRhWywgLTJdICAjIHRoaXMgY29sdW1uIGhhcyBleGNlc3NpdmUgbWlzc2luZyBkYXRhLg0KZGF0YSA8LSBkYXRhW2NvbXBsZXRlLmNhc2VzKGRhdGEpLCBdDQpyb3cubmFtZXMoZGF0YSkgPC0gMTpucm93KGRhdGEpICAjIHJlLWluZGV4IGZvciBzaW1wbGljaXR5Lg0KDQpEVDo6ZGF0YXRhYmxlKGhlYWQoZGF0YSwgNSksIG9wdGlvbnMgPSBsaXN0KHNjcm9sbFggPSBUUlVFKSkNCmBgYA0KDQoqKioNCg0KPGJyPg0KDQojIyBUcmFpbiBtb2RlbHMNCg0KKiAqKk91dGNvbWUqKjogcHJpY2UNCjxwPg0KKiAqKkZlYXR1cmVzKio6IH4yMA0KPHA+DQoqICoqU2FtcGxlIHNpemUqKjogfjIwMA0KPHA+DQoqICoqTW9kZWxzKio6IEEgTEFTU08gZnJvbSBgZ2xtbmV0YCBhbmQgYSBSYW5kb20gRm9yZXN0IGZyb20gYHJhbmRvbUZvcmVzdGAuDQoNCmBgYHtyfQ0Kb3V0Y29tZV9jb2wgPC0gd2hpY2gobmFtZXMoZGF0YSkgPT0gInByaWNlIikNCm91dGNvbWVfbmFtZSA8LSBuYW1lcyhkYXRhKVtvdXRjb21lX2NvbF0NCg0KbW9kZWxfZm9ybXVsYSA8LSBmb3JtdWxhKHBhc3RlMChvdXRjb21lX25hbWUsICAifiAuIikpDQoNCnNldC5zZWVkKDIyNCkNCm1vZGVsX2xhc3NvIDwtIGdsbW5ldDo6Y3YuZ2xtbmV0KHggPSBtb2RlbC5tYXRyaXgobW9kZWxfZm9ybXVsYSwgZGF0YSksIA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgeSA9IGFzLm1hdHJpeChkYXRhWywgb3V0Y29tZV9jb2wsIGRyb3AgPSBGQUxTRV0sIG5jb2wgPSAxKSkNCg0Kc2V0LnNlZWQoMjI0KQ0KbW9kZWxfcmYgPC0gcmFuZG9tRm9yZXN0OjpyYW5kb21Gb3Jlc3QoZm9ybXVsYSA9IG1vZGVsX2Zvcm11bGEsIGRhdGEgPSBkYXRhLCBudHJlZSA9IDIwMCkNCmBgYA0KDQoqKioNCg0KPGJyPg0KDQojIyBQcmVwYXJlIHNoYXBGbGV4OjpzaGFwRmxleCgpIElucHV0DQoNCiMjIyBVc2VyLWRlZmluZWQgcHJlZGljdGlvbiBmdW5jdGlvbg0KDQoqIFJlcXVpcmVkOiBBIHVzZXItZGVmaW5lZCB3cmFwcGVyIGZ1bmN0aW9uIHRoYXQgdGFrZXMgdGhlIGZvbGxvd2luZyAqKnBvc2l0aW9uYWwgYXJndW1lbnRzKio6DQogICAgKyAqKlBvc2l0aW9uIDEqKjogQSBsaXN0IG9mIG1vZGVsIG9iamVjdHMgZm9yIHByZWRpY3Rpbmcgb24gdGhlIGlucHV0IGRhdGFzZXQuDQogICAgKyAqKlBvc2l0aW9uIDIqKjogQSBkYXRhLmZyYW1lIG9mIG1vZGVsIGZlYXR1cmVzICh0aGUgb3V0Y29tZSBjb2x1bW4gd29uJ3QgYmUgcGFzc2VkIGluIGBzaGFwRmxleCgpYCkuICANCjxicj4NCmFuZCAqKnJldHVybnMqKjoNCjxicj4NCjxicj4NCiAgICArIEEgMS1jb2x1bW4gZGF0YS5mcmFtZSB3aXRoIGEgbnVtYmVyIG9mIHJvd3MgZXF1YWwgdG8gdGhlIGlucHV0IGRhdGEuDQo8cD4NCiogVGhpcyBmdW5jdGlvbiBjYW4gYmUgc2ltcGxlLS1saWtlIGJlbG93LS1vciBjb250YWluIG1ldGEtbW9kZWxzIGZvciBjb21iaW5pbmcgZW5zZW1ibGUgcHJlZGljdGlvbnMsIA0KZmVhdHVyZSB0cmFuc2Zvcm1hdGlvbnMsIG9yIG1vZGVsIHN0YWNraW5nIGV0Yy4NCg0KYGBge3J9DQojIG1vZGVsc1tbMV1dIGFuZCBtb2RlbHNbWzJdXSBjb3VsZCBiZSBoYXJkY29kZWQgbW9kZWxfbGFzc28gYW5kIG1vZGVsX3JmLg0KIyBJbiB0aGUgbmV4dCBjb2RlIGJsb2NrLCBzZWUgdGhlIGBtb2RlbF9saXN0YCBvYmplY3QgZm9yIGFuIGV4YW1wbGUgb2YgdGhlIGZvcm1hdCBvZiB0aGUgJ21vZGVscycgYXJndW1lbnQuDQpwcmVkaWN0X2Vuc2VtYmxlIDwtIGZ1bmN0aW9uKG1vZGVscywgZGF0YSwgLi4uKSB7DQogIA0KICB5X3ByZWRfbGFzc28gPC0gZGF0YS5mcmFtZShwcmVkaWN0KG1vZGVsc1tbMV1dLCBtb2RlbC5tYXRyaXgofiAuLCBkYXRhKSkpICAjIExBU1NPDQogIHlfcHJlZF9yZiA8LSBkYXRhLmZyYW1lKHByZWRpY3QobW9kZWxzW1syXV0sIGRhdGEpKSAgIyBSYW5kb20gRm9yZXN0DQogIA0KICBkYXRhX3ByZWQgPC0gZHBseXI6OmJpbmRfY29scyh5X3ByZWRfbGFzc28sIHlfcHJlZF9yZikNCiAgDQogIGRhdGFfcHJlZCA8LSBkYXRhLmZyYW1lKCJ5X3ByZWQiID0gcm93TWVhbnMoZGF0YV9wcmVkLCBuYS5ybSA9IFRSVUUpKQ0KICANCiAgcmV0dXJuKGRhdGFfcHJlZCkNCn0NCmBgYA0KDQoNCiMjIyBTaGFwbGV5IHNhbXBsaW5nIHBhcmFtZXRlcnMNCg0KKiBCZWxvdyBhcmUgc29tZSBvZiB0aGUgbWFpbiBhcmd1bWVudHMgdG8gYHNoYXBGbGV4OjpzaGFwRmxleCgpYCB3aXRoIHNvbWUgY29udGV4dC4NCg0KKiBXZSdyZSBnb2luZyB0byBleHBsYWluIGFsbCBpbnN0YW5jZXMgaW4gb3VyIGRhdGFzZXQgdXNpbmcgYWxsIGZlYXR1cmVzIHdoaWNoIGlzIHRoZSBkZWZhdWx0IA0Kc2V0dGluZy4NCg0KKiBSZWZlciB0byB0aGUtLWZvcnRoY29taW5nLS12aWduZXR0ZSB0byBzZWUgaG93IGBzaGFwRmxleDo6c2hhcEZsZXgoKWAgcnVudGltZSBhbmQgYWNjdXJhY3kgDQphcmUgYWZmZWN0ZWQgYnkgdGhlIG51bWJlciBvZiBtb2RlbCBmZWF0dXJlcyBhbmQgbW9udGUgY2FybG8gc2FtcGxlIHNpemUuDQoNCmBgYHtyfQ0KIyBBIGxpc3Qgb2YgZGF0YS5mcmFtZShzKSBvZiBtb2RlbCBmZWF0dXJlcyBzdWl0YWJsZSBmb3IgdGhlIHVzZXItZGVmaW5lZCBwcmVkaWN0IGZ1bmN0aW9uKHMpLg0KZGF0YV9saXN0IDwtIGxpc3QoZGF0YVssIC0ob3V0Y29tZV9jb2wpLCBkcm9wID0gRkFMU0VdKQ0KIyBEYXRhc2V0IHJvdyBudW1iZXJzIG9yIGluZGljaWVzLg0KZXhwbGFpbl9pbnN0YW5jZXMgPC0gMTpucm93KGRhdGEpDQojIEFyZSB0aGUgaW5zdGFuY2VzIHRvIGV4cGxhaW4gcm93IG51bWJlcnMvaW5kaWNlcyBvciByb3cgbmFtZXMgKCdyb3dfbmFtZScpIGluIHRoZSBpbnB1dCBkYXRhPw0KZXhwbGFpbl9pbnN0YW5jZV9pZCA8LSAicm93X2luZGV4Ig0KIyBBIGxpc3Qgb2Ygb2YgbW9kZWwgb2JqZWN0cy4gTmVzdGVkIGxpc3RzIG9mIGxlbmd0aChkYXRhX2xpc3QpIGFyZSBuZWVkZWQgaWYgbGVuZ3RoKGRhdGFfbGlzdCkgPiAxLg0KbW9kZWxfbGlzdCA8LSBsaXN0KG1vZGVsX2xhc3NvLCBtb2RlbF9yZikNCiMgQSBsaXN0IG9mIGxlbmd0aCAxIHZlY3RvcnMgd2l0aCBsZW5ndGgocHJlZGljdGlvbl9mdW5jdGlvbnMpID09IGxlbmd0aChkYXRhX2xpc3QpLg0KcHJlZGljdF9mdW5jdGlvbnMgPC0gbGlzdCgicHJlZGljdF9lbnNlbWJsZSIpDQojIFRoZSBudW1iZXIgb2YgcmFuZG9tbHkgc2VsZWN0ZWQgZGF0YXNldCByb3dzIHVzZWQgdG8gY2FsY3VsYXRlIHRoZSBmZWF0dXJlLWxldmVsIFNoYXBsZXkgdmFsdWVzLg0Kc2FtcGxlX3NpemUgPC0gMTAwDQojIE51bWJlciBvZiBjb3JlcyB0byB1c2UgaW4gcGFyYWxsZWw6Om1jbGFwcGx5KCk7IGxpbWl0ZWQgdG8gMSBvbiBXaW5kb3dzIE9TLg0Kbl9jb3JlcyA8LSBpZiAoU3lzLmluZm8oKVsic3lzbmFtZSJdID09ICJXaW5kb3dzIikgezF9IGVsc2Uge3BhcmFsbGVsOjpkZXRlY3RDb3JlcygpIC0gMX0NCmBgYA0KDQoqKioNCg0KPGJyPg0KDQojIyBzaGFwRmxleDo6c2hhcEZsZXgoKQ0KDQojIyMgRXhwbGFpbiB3aXRoIGFsbCBtb2RlbCBmZWF0dXJlcw0KDQoqIEJlY2F1c2UgYHNoYXBGbGV4OjpzaGFwRmxleCgpYCBleHBsYWlucyAxIGRhdGFzZXQgcm93L2luc3RhbmNlIGF0IGEgdGltZSwgd2UnbGwgbG9vcCB0aHJvdWdoIA0Kb3VyIGRhdGFzZXQgYW5kIHN0b3JlIHRoZSByZXN1bHRzIGluIGEgbGlzdC4NCg0KKiBMZXQncyBhbHNvIHJlY29yZCB0aGUgcnVudGltZSBhbmQgY29tcGFyZSBpdCB0byB0aGUgdGltZSBpdCB0YWtlcyB0byBleHBsYWluIHdpdGggMSBmZWF0dXJlLg0KDQpgYGB7cn0NCmV4cGxhaW5lZF9pbnN0YW5jZXMgPC0gdmVjdG9yKCJsaXN0IiwgbGVuZ3RoKGV4cGxhaW5faW5zdGFuY2VzKSkNCg0Kc3RhcnQgPC0gU3lzLnRpbWUoKQ0Kc2V0LnNlZWQoMjI0KQ0KZm9yIChpIGluIHNlcV9hbG9uZyhleHBsYWluX2luc3RhbmNlcykpIHsNCiAgDQogIGV4cGxhaW5lZF9pbnN0YW5jZXNbW2ldXSA8LSBzaGFwRmxleDo6c2hhcEZsZXgoZGF0YSA9IGRhdGFfbGlzdCwgDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZXhwbGFpbl9pbnN0YW5jZSA9IGV4cGxhaW5faW5zdGFuY2VzW2ldLCAgIyBsb29wDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZXhwbGFpbl9pbnN0YW5jZV9pZCA9IGV4cGxhaW5faW5zdGFuY2VfaWQsDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbW9kZWxzID0gbW9kZWxfbGlzdCwgDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcHJlZGljdF9mdW5jdGlvbnMgPSBwcmVkaWN0X2Z1bmN0aW9ucywgDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc2FtcGxlX3NpemUgPSBzYW1wbGVfc2l6ZSwgDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbl9jb3JlcyA9IG5fY29yZXMpDQp9DQpzdG9wIDwtIFN5cy50aW1lKCkNCmxpc3Qoc3RvcCAtIHN0YXJ0LCBwYXN0ZTAoIkNvcmVzID0gIiwgbl9jb3JlcykpDQpgYGANCg0KKioqDQoNCjxicj4NCg0KKiBUaGUgb3V0cHV0IG9mIGBzaGFwRmxleDo6c2hhcEZsZXgoKWAgaXMgYSBkYXRhLmZyYW1lIHdpdGggdGhlIGZvbGxvd2luZyBjb2x1bW5zOg0KICAgICsgKipleHBsYWluZWRfaW5zdGFuY2UqKjogVGhlIHJvdyBuYW1lIG9yIHJvdyBudW1iZXIgb2YgdGhlIHRhcmdldCBpbnN0YW5jZSAobnVtYmVyL25hbWUgZGVwZW5kcyBvbiB0aGUgJ2V4cGxhaW5faW5zdGFuY2VfaWRgIGFyZ3VtZW50KS4NCiAgICArICoqZmVhdHVyZV9uYW1lKio6IFRoZSBmZWF0dXJlIG5hbWUgZnJvbSBuYW1lcyhkYXRhKSBvciBhIHN1YnNldCBvZiBhbGwgZmVhdHVyZXMgaWYgdXNpbmcgdGhlICd0YXJnZXRfZmVhdHVyZXMnIGFyZ3VtZW50LiBUaGUgDQogICAgaW50ZXJjZXB0IHJlcHJlc2VudHMgdGhlIGF2ZXJhZ2UgcHJlZGljdGlvbiBpbiB0aGUgaW5wdXQgZGF0YXNldC0tcmVnYXJkbGVzcyBvZiB3aGV0aGVyIG9yIG5vdCBhbnkgbW9kZWxzIGV4cGxpY2l0bHkgdXNlIGludGVyY2VwdHMuDQogICAgKyAqKmZlYXR1cmVfdmFsdWUqKjogVGFrZW4gZnJvbSB0aGUgaW5wdXQgZGF0YS4gVGhlIGludGVyY2VwdCBoYXMgYW4gTkEgZmVhdHVyZSB2YWx1ZS4gQXQgcHJlc2VudCwgb25seSBhcHBlYXJzIHdpdGggMSBpbnB1dCBkYXRhc2V0Lg0KICAgICsgKipzaGFwX2VmZmVjdCoqOiBUaGUgYXZlcmFnZSBTaGFwbGV5IHZhbHVlIGFjcm9zcyBzYW1wbGVzIGluICdzYW1wbGVfc2l6ZScuDQogICAgKyAqKnNoYXBfZWZmZWN0X3NkKio6IFRoZSBzdGFuZGFyZCBkZXZpYXRpb24gaW4gU2hhcGxleSB2YWx1ZXMgYWNyb3NzIHNhbXBsZXMgaW4gJ3NhbXBsZV9zaXplJy4gQXQgcHJlc2VudCwgb25seSBhcHBlYXJzIHdpdGggMSBpbnB1dCBkYXRhc2V0Lg0KDQpgYGB7cn0NCmRhdGFfc2hhcCA8LSBkcGx5cjo6YmluZF9yb3dzKGV4cGxhaW5lZF9pbnN0YW5jZXMpDQoNCkRUOjpkYXRhdGFibGUoZGF0YV9zaGFwKQ0KYGBgDQoNCioqKg0KDQojIyMjIEdsb2JhbCBmZWF0dXJlIGVmZmVjdHMNCg0KKiBCZWxvdyBhcmUgcGxvdHMgc2ltaWxhciB0byBwYXJ0aWFsIGRlcGVuZGVuY2UgcGxvdHMgZm9yIGNhdGVnb3JpY2FsIGZvbGxvd2VkIGJ5IG51bWVyaWMgbW9kZWwgZmVhdHVyZXMuDQoNCmBgYHtyfQ0KZGF0YV9wbG90IDwtIGRhdGFfc2hhcA0KDQpmYWN0b3JfZmVhdHVyZXMgPC0gbmFtZXMoZGF0YSlbd2hpY2godW5saXN0KGxhcHBseShkYXRhLCBmdW5jdGlvbih4KSB7bWV0aG9kczo6aXMoeCwgImZhY3RvciIpfSkpKV0NCg0KZGF0YV9wbG90IDwtIGRwbHlyOjpmaWx0ZXIoZGF0YV9wbG90LCBmZWF0dXJlX25hbWUgJWluJSBmYWN0b3JfZmVhdHVyZXMpDQoNCnAgPC0gZ2dwbG90KGRhdGFfcGxvdCwgYWVzKGZlYXR1cmVfdmFsdWUsIHNoYXBfZWZmZWN0KSkNCnAgPC0gcCArIGdlb21fYm94cGxvdCgpDQpwIDwtIHAgKyBzY2FsZV95X2NvbnRpbnVvdXMobGFiZWwgPSBzY2FsZXM6OmRvbGxhcikNCnAgPC0gcCArIGZhY2V0X3dyYXAofiBmZWF0dXJlX25hbWUsIHNjYWxlcyA9ICJmcmVlIikNCnAgPC0gcCArIHRoZW1lX2J3KCkgKyB4bGFiKE5VTEwpICsgeWxhYigiU2hhcGxleSB2YWx1ZSAoMCBpcyB0aGUgYXZlcmFnZSBwcmVkaWN0aW9uKSIpDQpwDQpgYGANCg0KKioqDQoNCmBgYHtyLCByZXN1bHRzID0gImhpZGUifQ0KZGF0YV9wbG90IDwtIGRhdGFfc2hhcA0KDQpudW1lcmljX2ZlYXR1cmVzIDwtIG5hbWVzKGRhdGEpW3doaWNoKHVubGlzdChsYXBwbHkoZGF0YSwgZnVuY3Rpb24oeCkgeyFtZXRob2RzOjppcyh4LCAiZmFjdG9yIil9KSkpXQ0KDQpkYXRhX3Bsb3QgPC0gZHBseXI6OmZpbHRlcihkYXRhX3Bsb3QsIGZlYXR1cmVfbmFtZSAlaW4lIG51bWVyaWNfZmVhdHVyZXMpDQoNCmRhdGFfcGxvdCRmZWF0dXJlX3ZhbHVlIDwtIGFzLm51bWVyaWMoZGF0YV9wbG90JGZlYXR1cmVfdmFsdWUpDQoNCnAgPC0gZ2dwbG90KGRhdGFfcGxvdCwgYWVzKGZlYXR1cmVfdmFsdWUsIHNoYXBfZWZmZWN0KSkNCnAgPC0gcCArIGdlb21fcG9pbnQoYWxwaGEgPSAuMjUpDQpwIDwtIHAgKyBnZW9tX3Ntb290aCgpDQpwIDwtIHAgKyBzY2FsZV95X2NvbnRpbnVvdXMobGFiZWwgPSBzY2FsZXM6OmRvbGxhcikNCnAgPC0gcCArIGZhY2V0X3dyYXAofiBmZWF0dXJlX25hbWUsIHNjYWxlcyA9ICJmcmVlIikNCnAgPC0gcCArIHRoZW1lX2J3KCkgKyB4bGFiKE5VTEwpICsgeWxhYigiU2hhcGxleSB2YWx1ZSAoMCBpcyB0aGUgYXZlcmFnZSBwcmVkaWN0aW9uKSIpDQpzdXBwcmVzc1dhcm5pbmdzKHN1cHByZXNzTWVzc2FnZXMocHJpbnQocCkpKQ0KYGBgDQoNCioqKg0KDQojIyMgRXhwbGFpbiB3aXRoIDEgbW9kZWwgZmVhdHVyZQ0KDQoqIE5vdywgbGV0J3Mgc2F5IHdlJ3JlIHJlYWxseSBpbnRlcmVzdGVkIGluIHRoZSBtYXJnaW5hbCBlZmZlY3Qgb2YgaG9yc2Vwb3dlciBvbiBjYXIgcHJpY2VzIGJ1dCBkb24ndCANCmhhdmUgdGhlIHRpbWUgdG8gY29tcHV0ZSBTaGFwbGV5IHZhbHVlcyBmb3IgYWxsIGZlYXR1cmVzLg0KDQoqIEluIHRoaXMgY2FzZSwgd2UnbGwgc2V0IHRoZSAndGFyZ2V0X2ZlYXR1cmVzJyBhcmd1bWVudCBhbmQgZXhhbWluZSBpdHMgZWZmZWN0Lg0KDQoqIFRoZSBTaGFwbGV5IHZhbHVlcyBhcmUgc3RpbGwgY2FsY3VsYXRlZCBpbiB0aGUgdXN1YWwgd2F5LCBhbmQgdGhlICoqcmVzdWx0cyBhcmUgaWRlbnRpY2FsKiogaWYgYSBzZWVkIGlzIHNldCwgDQpidXQgd2UgKipnZXQgcmVzdWx0cyAxNCB0aW1lcyBmYXN0ZXIqKi4NCg0KYGBge3J9DQpleHBsYWluZWRfaW5zdGFuY2VzIDwtIHZlY3RvcigibGlzdCIsIGxlbmd0aChleHBsYWluX2luc3RhbmNlcykpDQoNCnRhcmdldF9mZWF0dXJlcyA8LSBsaXN0KCJob3JzZXBvd2VyIikNCg0Kc3RhcnQgPC0gU3lzLnRpbWUoKQ0Kc2V0LnNlZWQoMjI0KQ0KZm9yIChpIGluIHNlcV9hbG9uZyhleHBsYWluX2luc3RhbmNlcykpIHsNCg0KICBleHBsYWluZWRfaW5zdGFuY2VzW1tpXV0gPC0gc2hhcEZsZXg6OnNoYXBGbGV4KGRhdGEgPSBkYXRhX2xpc3QsIA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGV4cGxhaW5faW5zdGFuY2UgPSBleHBsYWluX2luc3RhbmNlc1tpXSwgICMgbG9vcA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGV4cGxhaW5faW5zdGFuY2VfaWQgPSBleHBsYWluX2luc3RhbmNlX2lkLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1vZGVscyA9IG1vZGVsX2xpc3QsIA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHByZWRpY3RfZnVuY3Rpb25zID0gcHJlZGljdF9mdW5jdGlvbnMsIA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHRhcmdldF9mZWF0dXJlcyA9IHRhcmdldF9mZWF0dXJlcywgDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc2FtcGxlX3NpemUgPSBzYW1wbGVfc2l6ZSwgDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbl9jb3JlcyA9IG5fY29yZXMpDQp9DQpzdG9wIDwtIFN5cy50aW1lKCkNCmxpc3Qoc3RvcCAtIHN0YXJ0LCBwYXN0ZTAoIkNvcmVzID0gIiwgbl9jb3JlcykpDQpgYGANCg0KKioqDQoNCiMjIyMgR2xvYmFsIGZlYXR1cmUgZWZmZWN0cw0KDQpgYGB7ciwgcmVzdWx0cyA9ICJoaWRlIn0NCmRhdGFfc2hhcF92YXIgPC0gZHBseXI6OmJpbmRfcm93cyhleHBsYWluZWRfaW5zdGFuY2VzKQ0KDQpkYXRhX3Bsb3QgPC0gZGF0YV9zaGFwX3Zhcg0KDQpudW1lcmljX2ZlYXR1cmVzIDwtICJob3JzZXBvd2VyIg0KDQpkYXRhX3Bsb3QgPC0gZHBseXI6OmZpbHRlcihkYXRhX3Bsb3QsIGZlYXR1cmVfbmFtZSAlaW4lIG51bWVyaWNfZmVhdHVyZXMpDQoNCmRhdGFfcGxvdCRmZWF0dXJlX3ZhbHVlIDwtIGFzLm51bWVyaWMoZGF0YV9wbG90JGZlYXR1cmVfdmFsdWUpDQoNCnAgPC0gZ2dwbG90KGRhdGFfcGxvdCwgYWVzKGZlYXR1cmVfdmFsdWUsIHNoYXBfZWZmZWN0KSkNCnAgPC0gcCArIGdlb21fcG9pbnQoYWxwaGEgPSAuMjUpDQpwIDwtIHAgKyBnZW9tX3Ntb290aCgpDQpwIDwtIHAgKyBzY2FsZV95X2NvbnRpbnVvdXMobGFiZWwgPSBzY2FsZXM6OmRvbGxhcikNCnAgPC0gcCArIGZhY2V0X3dyYXAofiBmZWF0dXJlX25hbWUsIHNjYWxlcyA9ICJmcmVlIikNCnAgPC0gcCArIHRoZW1lX2J3KCkgKyB4bGFiKE5VTEwpICsgeWxhYigiU2hhcGxleSB2YWx1ZSAoMCBpcyB0aGUgYXZlcmFnZSBwcmVkaWN0aW9uKSIpDQpzdXBwcmVzc1dhcm5pbmdzKHN1cHByZXNzTWVzc2FnZXMocHJpbnQocCkpKQ0KYGBgDQoNCioqKg0KDQojIyMgRmVhdHVyZSBzdWJzZXQgY29uc2lzdGVuY3kNCg0KKiBGaW5hbGx5LCB3ZSdsbCBjaGVjayB0byBzZWUgdGhhdCB0aGUgaG9yc2Vwb3dlciBTaGFwbGV5IHZhbHVlIGVzdGltYXRlcyBhY3Jvc3Mgb3VyIHNhbXBsZXMgYXJlIA0KaWRlbnRpY2FsIHdoZW4gU2hhcGxleSB2YWx1ZXMgYXJlIChhKSBjb21wdXRlZCBmb3IgYWxsIGZlYXR1cmVzIGFuZCAoYikgY29tcHV0ZWQgc29sZXkgZm9yIGhvcnNlcG93ZXIuDQoNCiogQXMgZXhwZWN0ZWQsICoqdGhlIGVzdGltYXRlcyBhcmUgaWRlbnRpY2FsKiouIElmIHdlIGFyZSBpbnRlcmVzdGVkIGluIGZvY3VzaW5nIG9uIGhvcnNlcG93ZXIgYW5kIA0KbGVhcm5pbmcgbW9yZSBhYm91dCBob3cgdGhlIHJlbGF0aW9uc2hpcCBiZXR3ZWVuIGhvcnNlcG93ZXIgYW5kIGEgY2FyJ3MgcHJpY2UgY2hhbmdlcyBhcyAoYSkgbmV3IG1vZGVscyANCmFyZSBhZGRlZCB0byB0aGUgZW5zZW1ibGUgb3IgKGIpIHRoZSBtb2RlbCBpbmNvcnBvcmF0ZXMgbmV3IGZlYXR1cmVzLCB3ZSBjYW4gZG8gc28gd2l0aG91dCB0aGUgDQpvdmVyaGVhZCBvZiBjb21wdXRpbmcgU2hhcGxleSB2YWx1ZXMgZm9yIGFsbCBmZWF0dXJlcy4NCg0KYGBge3J9DQpob3JzZXBvd2VyX3NoYXBfYWxsX2ZlYXR1cmVzIDwtIGRwbHlyOjpmaWx0ZXIoZGF0YV9zaGFwLCBmZWF0dXJlX25hbWUgPT0gImhvcnNlcG93ZXIiKSAlPiUgDQogIGRwbHlyOjpzZWxlY3Qoc2hhcF9lZmZlY3QpDQpob3JzZXBvd2VyX3NoYXBfMV9mZWF0dXJlIDwtIGRwbHlyOjpmaWx0ZXIoZGF0YV9zaGFwX3ZhciwgZmVhdHVyZV9uYW1lID09ICJob3JzZXBvd2VyIikgJT4lIA0KICBkcGx5cjo6c2VsZWN0KHNoYXBfZWZmZWN0KQ0KDQppZGVudGljYWwoaG9yc2Vwb3dlcl9zaGFwX2FsbF9mZWF0dXJlcywgaG9yc2Vwb3dlcl9zaGFwXzFfZmVhdHVyZSkNCmBgYA0KDQoqKioNCg0KIyMjIExvY2FsIGZlYXR1cmUgaW1wb3J0YW5jZQ0KDQoqIEJlY2F1c2UgU2hhcGxleSB2YWx1ZXMgZ2l2ZSB1cyBpbnNpZ2h0IGludG8gaG93IGVhY2ggZmVhdHVyZSB1bmlxdWVseSBhZmZlY3RzIGVhY2ggaW5zdGFuY2UncyBwcmVkaWN0aW9uLCANCndlJ2xsIHByb2R1Y2UgYSBwbG90IG9mIHRoZSBmZWF0dXJlIGVmZmVjdHMgcHJvZmlsZSBmb3IgYSBoYW5kZnVsIG9mIGluc3RhbmNlcy4NCg0KKiBCZWxvdyBpcyBhIHBsb3Qgb2YgaG93IGVhY2ggb2YgdGhlIG1vZGVsZWQgZmVhdHVyZXMgZnJvbSBvdXIgZW5zZW1ibGUgbW9kZWwgaXMgaW1wYWN0aW5nIHByZWRpY3RlZCBwcmljZXMgDQpmb3IgdGhlIDYgQXVkaXMgaW4gdGhlIGRhdGFzZXQgKHJvd3MgNCB0aHJvdWdoIDkgaW4gb3VyIGZpbHRlcmVkIGRhdGFzZXQpLg0KDQoqIEhvdmVyIG92ZXIgdGhlIGJhcnMgdG8gc2VlIHRoZSBmZWF0dXJlIHZhbHVlcy4NCg0KYGBge3IsIGZpZy53aWR0aCA9IDh9DQpkYXRhX3Bsb3QgPC0gZGF0YV9zaGFwDQoNCmF1ZGlzIDwtIHdoaWNoKGRhdGEkbWFrZSA9PSAiYXVkaSIpDQoNCmRhdGFfcGxvdCA8LSBkcGx5cjo6ZmlsdGVyKGRhdGFfcGxvdCwgZXhwbGFpbmVkX2luc3RhbmNlICVpbiUgYXVkaXMpDQoNCmRhdGFfcGxvdCRiYXJfY29sb3IgPC0gaWZlbHNlKGRhdGFfcGxvdCRzaGFwX2VmZmVjdCA+PSAwLCAiaW5jcmVhc2UiLCAiZGVjcmVhc2UiKQ0KDQpwIDwtIGdncGxvdChkYXRhX3Bsb3QsIGFlcyh4ID0gZmVhdHVyZV9uYW1lLCB5ID0gc2hhcF9lZmZlY3QsIGZpbGwgPSBiYXJfY29sb3IsIA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgZ3JvdXAgPSBleHBsYWluZWRfaW5zdGFuY2UsIHRleHQgPSBwYXN0ZTAoZmVhdHVyZV9uYW1lLCAiOiAiLCBmZWF0dXJlX3ZhbHVlKSkpDQpwIDwtIHAgKyBnZW9tX2JhcihzdGF0ID0gImlkZW50aXR5Iiwgc2hvdy5sZWdlbmQgPSBGQUxTRSkNCnAgPC0gcCArIHNjYWxlX3lfY29udGludW91cyhsYWJlbCA9IHNjYWxlczo6ZG9sbGFyKQ0KcCA8LSBwICsgZmFjZXRfd3JhcCh+IGV4cGxhaW5lZF9pbnN0YW5jZSkNCnAgPC0gcCArIHRoZW1lX2J3KCkgKyB0aGVtZShsZWdlbmQucG9zaXRpb24gPSAibm9uZSIpICsgY29vcmRfZmxpcCgpICsgeGxhYihOVUxMKSArIHlsYWIoIlNoYXBsZXkgdmFsdWUiKQ0KcGxvdGx5OjpnZ3Bsb3RseShwLCB0b29sdGlwID0gInRleHQiKQ0KYGBgDQoNCioqKg0KDQo=